import java.util.Vector;
import java.util.Stack;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import javax.swing.JTextArea;

/**
 * GraphAlg class contains various graph algorithm defined as static methods.
 * All these method operate on GraphADT<VertexAttr, EdgeAttr>.
 * 
 * @version 1.0
 * @author K.Vamsi Krishna
 */
public final class GraphAlg
{
	// refers to the text area into which the algorithms may display their messages.
	private static JTextArea messagePanel;
	// refers to the text area into which the algorithms may display their help.
	private static JTextArea helpPanel;
	
	/**
	 * Sets the messagePanel for the algorithms.
	 */
	public static void setMessagePanel(JTextArea messagePanel)
	{
		GraphAlg.messagePanel = messagePanel;
	}
	
	/**
	 * Sets the helpPanel for the algorithms.
	 */
	public static void setHelpPanel(JTextArea helpPanel)
	{
		GraphAlg.helpPanel = helpPanel;
	}
	
	// Used by algorithms to display the help file, 'fileName', in the helpPanel.
	private static void showHelp(String fileName)
	{
		try
		{
			BufferedReader helpfile = new BufferedReader(new FileReader(fileName));
			String line;
			
			// clear the helpPanel
			helpPanel.setText("");
			
			while((line = helpfile.readLine()) != null)
				helpPanel.append(line + "\n");
		}
		catch(IOException e)
		{
			System.out.println("Error : Unable to open " + fileName + ".");
		}
	}
	
	/**
	 * Finds an Hamilton tour in the given graph.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph for which Hamilton tours should be found. G may be directed or undirected but must be connected.
	 * @param tour Is the Integer Vector reference into which the tour is returned as a sequence of vertices to be visited.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 * @return True if able to find a tour, otherwise returns false.
	 */
	public static boolean HamiltonTour(GraphADT<VertexAttr, EdgeAttr> G, Vector<Integer> tour, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		boolean visited[] = new boolean[G.numVertices()];
		boolean tried[][] = new boolean[G.numVertices()][G.numVertices()];
		Vector<Integer> nl;
		boolean retValue = true;
		int i, j;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/HamiltonTour.txt");
			messagePanel.setText("Start.");
		}
				
		try
		{
			if(!GraphAlg.isConnected(G))
				throw new GraphAlgException("Hamilton tour doesnot exist in unconnected graphs");
			
			for(i = 0; i < G.numVertices(); i++)
				visited[i] = false;
				
			// show message
			if(showMessages)
			{
				for(i = 0; i < G.numVertices(); i++)
					messagePanel.append("\n" + G.getVertex(i).getName());
			}
			
			for(i = 0; i < G.numVertices(); i++)
				for(j = 0; j < G.numVertices(); j++)
					tried[i][j] = false;

			tour.add(0);
			visited[0] = true;
		
			while(true)
			{
				if(tour.size() == G.numVertices()) // found a tour
					break;
					
				nl = G.getNeighbours(tour.lastElement());
				for(i = 0; i < nl.size(); i++)
				{
					if(visited[nl.get(i)] == false && tried[tour.lastElement()][nl.get(i)] == false)
					{
						 // special check when adding last vertex, it should reach 0 again
						if(tour.size() == G.numVertices()-1)
						{
							if(G.edgeExists(nl.get(i), 0))
								break;
						}
						else
							break;
					}
				}
				if(i < nl.size()) // found an untried neighbour
				{
					tried[tour.lastElement()][nl.get(i)] = true;
					tour.add(nl.get(i));
					visited[nl.get(i)] = true;
					// show message
					if(showMessages)
						messagePanel.append("\nnext vertex is " + G.getVertex(nl.get(i)).getName());
				}
				else // backtrack
				{
					if(tour.lastElement().intValue() == 0) // backtrack from vertex 0 indicates that no tour exists.
					{
						// show message
						if(showMessages)
							messagePanel.append("\nbacktracking from " + G.getVertex(0).getName());

						retValue = false;
						break;
					}
									
					visited[tour.lastElement()] = false;
					for(j = 0; j < G.numVertices(); j++)
						tried[tour.lastElement()][j] = false;
					// show message
					if(showMessages)
						messagePanel.append("\nbacktracking from " + G.getVertex(tour.lastElement()).getName());
					tour.remove(tour.size()-1);
				}
			}

			if(retValue == true)
			{
				tour.add(0);
				
				for(i = 0; i < tour.size()-1; i++)
					animationStr.add("E"+tour.get(i)+","+tour.get(i+1));
					
				// show message
				if(showMessages)
				{
					String tourStr = new String();
					for(int touri = 0; touri < tour.size(); touri++ )
						tourStr += G.getVertex(tour.get(touri)).getName() + ",";
					tourStr = new String(new StringBuffer(tourStr).deleteCharAt(tourStr.length()-1));
					messagePanel.append("\nHamilton tour found :" + tourStr);
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.HamiltonTour");
			retValue = false;
		}
		
		animationStr.add("END");
		// show message
		if(!retValue)
			if(showMessages)
				messagePanel.append("\n Unable to find hamilton tour.");
		if(showMessages)
			messagePanel.append("\n" + "End.");	
		return retValue;
	}
	
	// used by TravellingSalesmanProblem
	private static int gTSP(int i, Vector<Integer> S, int s, int cost[][], Vector<Integer> j)
	{
		int min;
		int mini;
		int k;
		
		if(S.size() == 0)
		{
			j.add(0,s);
			return cost[i][s];	
		}
		else
		{
			min = 10000;
			mini = 0;
			for(k = 0; k < S.size(); k++)
			{
				Integer kth = S.get(k);
				S.remove(kth);
				
				int xcost = gTSP(kth, S, s, cost, j);
				if(min > cost[i][kth] + xcost)
				{
					min = cost[i][kth] + xcost;
					mini = k;
				}
				
				S.add(k, kth);
			}
			j.add(0, S.get(mini));
			return min;
		}
	}
	/**
	 * Travelling Salesman Problem. Finds a shortest tour connecting all the vertices.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph to be colored. G may be directed or undirected.
	 * @param s Is the start vertex.
	 * @param tour Is the Integer Vector reference into which the tour is returned as a sequence of vertices to be visited.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 * @return True if able to find a TSP tour, false otherwise.
	 */
	public static boolean TravellingSalesmanProblem(GraphADT<VertexAttr, EdgeAttr> G, int s, Vector<Integer> tour, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		Vector<Integer> S = new Vector<Integer>();
		int cost[][] = new int[G.numVertices()][G.numVertices()];
		int i,j;
		Integer cs = new Integer(s);
		Vector<Integer> nextv = new Vector<Integer>();
		boolean retValue = true;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/TravellingSalesmanProblem.txt");
			messagePanel.setText("Start.");
		}
				
		try
		{
			if(!GraphAlg.isConnected(G))
				throw new GraphAlgException("TSP tour doesnot exist in unconnected graphs");
			
			for(i = 0; i < G.numVertices(); i++)
				for(j =0; j < G.numVertices(); j++)
					if(G.edgeExists(i, j))
						cost[i][j] = G.getEdge(i, j).getWeight();
					else if(i == j)
						cost[i][j] = 0;
					else
						cost[i][j] = 10000;
					
			for(i = 0; i < G.numVertices(); i++)
				S.add(i);
			
			cs = new Integer(cs);
			tour.add(cs);
			while(S.size()!=0)
			{
				S.remove(cs);
				gTSP(cs, S, s, cost, nextv);
				if(!G.edgeExists(cs, nextv.get(0)))
				{
					retValue = false;
					break;
				}
				tour.add(nextv.get(0));
				cs = nextv.get(0);			
			}
			
			if(retValue == true)
			{
				for(i = 0; i < tour.size()-1; i++)
					animationStr.add("E"+tour.get(i)+","+tour.get(i+1));
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.TravellingSalesmanProblem");
			retValue = false;
		}
		
		animationStr.add("END");
		// show message
		if(!retValue)
			if(showMessages)
				messagePanel.append("\nUnable to find TSP tour.");
		if(showMessages)
			messagePanel.append("\n" + "End.");					
		return retValue;
	}	
	
	/**
	 * Graph Coloring. Colors all the vertices of the given graph. Colors are numbered from 0 to m-1.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph to be colored. G should be undirected.
	 * @param m Is the maximum number of colors to be used.
	 * @param coloring Is the int array reference into which the function returns the color of each vertex.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 * @return True if able to find a coloring, otherwise returns false.
	 */
	public static boolean GraphColoring(GraphADT<VertexAttr, EdgeAttr> G, int m, int coloring[], Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		boolean retValue = true;
		int i, j;

		// show help and clear message
		if(showMessages)
		{
			showHelp("help/GraphColoring.txt");
			messagePanel.setText("Start.");
		}
				
		try
		{
			if(G.isDirected())
				throw new GraphAlgException("Graph Coloring doesnot make sense on directed graphs");
				
			for(i = 0; i < G.numVertices(); i++)
				coloring[i] = -1;
				
			// show message
			if(showMessages)
			{
				for(i = 0; i < G.numVertices(); i++)
					messagePanel.append("\n" + G.getVertex(i).getName());
			}

			for(i = 0; i < G.numVertices() && retValue; i++)
			{
				// find a valid color greater than coloring[i]
				while(true)
				{
					coloring[i]++;
					
					// show message
					if(showMessages)
						messagePanel.append("\ntrying to color " + G.getVertex(i).getName() + " with " + coloring[i]);
					
					// check if all colors are exhausted 
					if(i == 0 && coloring[i] == m) // cannot backtrack from 0
					{
						// show message
						if(showMessages)
							messagePanel.append("\nbacktracking from " + G.getVertex(0).getName());
						retValue = false;
						break;
					}
					
					if(coloring[i] == m) // backtrack
					{
						// show message
						if(showMessages)
							messagePanel.append("\nbacktracking from " + G.getVertex(i).getName() + " to " + G.getVertex(i-1).getName());
						coloring[i] = -1;
						i -= 2;
						break;	
					}
					
					for(j = 0; j < G.numVertices(); j++)
					{
						if(G.edgeExists(i,j) && coloring[i] == coloring[j])
							break;							
					}
					// found a valid color
					if(j == G.numVertices())
						break;
				}
			}
			
			if(retValue)
			{
				// show message
				if(showMessages)
				{
					String colorStr = new String();
					for(int colori = 0; colori != G.numVertices(); colori++)
						colorStr += G.getVertex(colori).getName() + "(" + coloring[colori] + "),";
					colorStr = new String(new StringBuffer(colorStr).deleteCharAt(colorStr.length()-1));
					messagePanel.append("\nGraph coloring found :" + colorStr);
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.GraphColoring");
			retValue = false;
		}
		
		animationStr.add("END");
		// show message
		if(!retValue)
			if(showMessages)
				messagePanel.append("\n" + "Unable to color the graph.");

		if(showMessages)
			messagePanel.append("\n" + "End.");	
		return retValue;
	}	
	
	/**
	 * Critical Path Analysis. Does Critical path analysis on the given
	 * graph(regarded as a scheduling graph), and finds EST and LST at each vertex.
	 * Slack may be calculated from EST and LST, Slack = LST - EST.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph(regarded as scheduling graph) on which CPA should be done. G should directed acyclic graph.
	 * @param s Is the start vertex.
	 * @param t Is the finish vertex.
	 * @param cpath Is the Integer Vector reference into which the critical path found is returned.
	 * @param est Is the int array reference into which EST of all the vertices is returned.
	 * @param lst Is the int array reference into which LST of all the vertices is returned.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 */
	public static void CriticalPathAnalysis(GraphADT<VertexAttr, EdgeAttr> G, int s, int t, Vector<Integer> cpath, int est[], int lst[], Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		Vector<Integer> topSort = new Vector<Integer>();
		Vector<Integer> path = new Vector<Integer>();
		Vector<String> as = new Vector<String>();
		Vector<Integer> nl = new Vector<Integer>();
		int i,j;
		int temp;

		// show help and clear message
		if(showMessages)
		{
			showHelp("help/CriticalPathAnalysis.txt");
			messagePanel.setText("Start.");
		}
				
		try
		{
			TopologicalSort(G, topSort, as, false);
		
			for(i = 0; i < G.numVertices(); i++)
			{
				if(topSort.get(i) != s)
					LongestPath(G, s, topSort.get(i), path, as, false);
				else
					path.add(s);
				
				temp = 0;
				j=0;
				while(true)
				{
					if(path.get(j) == topSort.get(i))
						break;
					temp += G.getEdge(path.get(j),path.get(j+1)).getWeight();
					j++;
				}
				est[topSort.get(i)] = temp;
				
				if(topSort.get(i) == t)
				{
					for(j = 0; j < G.numVertices(); j++)
						cpath.add(path.get(j));
				}
			}
		
			for(i = G.numVertices()-1; i >= 0; i--)
			{
				if(topSort.get(i) == t)
				{
					lst[topSort.get(i)] = est[topSort.get(i)];
				}
				else
				{
					nl = G.getNeighbours(topSort.get(i));
					lst[topSort.get(i)] = lst[nl.get(0)]-G.getEdge(topSort.get(i),nl.get(0)).getWeight();
					for(j = 1; j < nl.size(); j++)
					{
						lst[topSort.get(i)] = Math.min(lst[nl.get(j)]-G.getEdge(topSort.get(i),nl.get(j)).getWeight(), lst[topSort.get(i)]);
					}
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.CriticalPathAnalysis");
		}
		
		animationStr.add("END");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");		
	}
	
	/**
	 * Maximum Flow Algorithm. Finds the maximum flow possible from source to sink.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph for which maximum flow should be computed. G should be a directed graph.
	 * @param s Is the source vertex. It's indegree should be 0.
	 * @param t Is the sink vertex. It's outdegree should be 0.
	 * @param flow Is used for returning the flow matrix computed. Each element indicates the flow on the corresponding edge, if it exists.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 */
	public static void MaximumFlow(GraphADT<VertexAttr, EdgeAttr> G, int s, int t, int flow[][], Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		int capacity[][] = new int[G.numVertices()][G.numVertices()];
		boolean labelled[] = new boolean[G.numVertices()];
		int predecessor[] = new int[G.numVertices()];
		// true for forward edges and false for backward edges
		boolean edgeflag[] = new boolean[G.numVertices()];
		int augment[] = new int[G.numVertices()];
		Vector<Integer> nl;
		Vector<Integer> nfl;
		int a;
		int i,j,k;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/MaximumFlow.txt");
			messagePanel.setText("Start.");
		}
				
		try
		{
			if(!G.isDirected())
				throw new GraphAlgException("Maximum Flow works on directed graphs only");
			if(G.inDegree(s) != 0)
				throw new GraphAlgException("Wrong source vertex is specified");
			if(G.outDegree(t) != 0)
				throw new GraphAlgException("Wrong sink vertex is specified");

			for(i = 0; i < G.numVertices(); i++)
				for(j = 0; j < G.numVertices(); j++)
					if(G.edgeExists(i,j))
						capacity[i][j] = G.getEdge(i,j).getWeight();
					else
						capacity[i][j] = 0;
						
			while(true)
			{
				// labelling
			
				for(i = 0; i < G.numVertices(); i++)
				{
					labelled[i] = false;
					predecessor[i] = -1;
					augment[i] = 0;
				}
			
				k = s;
				labelled[k] = true;
				predecessor[k] = -1;
				augment[k] = 10000;
				do
				{
					// forward edge
					nl = G.getNeighbours(k);
					for(i = 0; i < nl.size(); i++)
						if(flow[k][nl.get(i)] < capacity[k][nl.get(i)] && labelled[nl.get(i)] == false)
							break;
					if(i < nl.size())
					{
						labelled[nl.get(i)] = true;
						predecessor[nl.get(i)] = k;
						edgeflag[nl.get(i)] = true;
						augment[nl.get(i)] = Math.min(capacity[k][nl.get(i)] - flow[k][nl.get(i)],augment[k]);
						k = nl.get(i);
					}
					else
					{
						// backward edge
						nfl = G.getNeighbourFor(k);
						for(i = 0; i < nfl.size(); i++)
							if(flow[nfl.get(i)][k] > 0 && labelled[nfl.get(i)] == false)
								break;
							
						if(i < nfl.size())
						{
							labelled[nfl.get(i)] = true;
							predecessor[nfl.get(i)] = k;
							edgeflag[nfl.get(i)] = false;
							augment[nfl.get(i)] = Math.min(flow[nfl.get(i)][k],augment[k]);
							k = nfl.get(i);
						}
						else
						{
							// backtrack
							if(k == s)
								break;
							else
								k = predecessor[k];
						}
					}
				}while(!labelled[t]);
				
				// flow augmenting
				if(k != s)
				{
					// show message
					if(showMessages)
					{
						String fapStr = new String();
						int mi;
						for(mi = t; mi != -1; mi = predecessor[mi])
						{
							fapStr += G.getVertex(mi).getName() + ",";
						}
						fapStr = new String((new StringBuffer(fapStr)).deleteCharAt(fapStr.length()-1).reverse());
						
						messagePanel.append("\nfound a flow augmenting path: " + fapStr);
					}
					
					// show message
					if(showMessages)
						messagePanel.append("\naugmenting it...");
					i = t;
					a = augment[t];
					while(true)
					{
						if(edgeflag[i] == true)
						{
							// show message
							if(showMessages)
								messagePanel.append("\nforward, old flow = " + flow[predecessor[i]][i] + ", new flow = " +  (flow[predecessor[i]][i]+a));
							flow[predecessor[i]][i] += a;
						}
						else
						{
							// show message
							if(showMessages)
								messagePanel.append("\nbackward, old flow = " + flow[i][predecessor[i]] + ", new flow = " +  (flow[i][predecessor[i]]-a));
							flow[i][predecessor[i]] -= a;
						}
								
						i = predecessor[i];
						if(i == s)
							break;
					}
				}
				else
				{
					messagePanel.append("\nNo more flow augmenting paths.");
					break;
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.MaximumFlow");
		}
		
		animationStr.add("END");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");		
	}

	/**
	 * Longest Path Algorithm.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph on which algorithm is run. G should be directed and acyclic.
	 * @param s Is the source vertex.
	 * @param t Is the destination vertex.
	 * @param path Is the Integer Vector reference into which the function returns the vertices on the path found.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 * @return True if it is able to find longest path.
	 */
	public static boolean LongestPath(GraphADT<VertexAttr, EdgeAttr> G, int s, int t, Vector<Integer> path, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		boolean permanent[] = new boolean[G.numVertices()];
		int predecessor[] = new int[G.numVertices()];
		int distance[] = new int[G.numVertices()];
		int weight[][] = new int[G.numVertices()][G.numVertices()];
		int revpath[] = new int[G.numVertices()];
		Vector<Integer> nfl = new Vector<Integer>();
		int i,j;
		boolean retValue = true;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/LongestPath.txt");
			messagePanel.setText("Start.");
		}
				
		try
		{
			if(!G.isDirected() || !isAcyclic(G))
				throw new GraphAlgException("Longest Path can run on directed acyclic graphs only");
				
			for(i = 0; i < G.numVertices(); i++)
				for(j = 0; j < G.numVertices(); j++)
					if(G.edgeExists(i,j))
						weight[i][j] = G.getEdge(i,j).getWeight();
					else
						weight[i][j] = 0;
						
			for(i = 0; i < G.numVertices(); i++)
			{
				permanent[i] = false;
				distance[i] = -1;
			}
			
			permanent[s] = true;
			animationStr.add("V"+s);
			predecessor[s] = -1;
			distance[s] = 0;
			// show message
			if(showMessages)
				messagePanel.append("\n" + G.getVertex(s).getName() + " is made permanent, with disatnce " + distance[s] + ".");
			do
			{
				for(i = 0; i < G.numVertices(); i++)
				{
					if(permanent[i] == false)
					{
						nfl = G.getNeighbourFor(i);
						
						for(j = 0; j < nfl.size(); j++)
							if(permanent[nfl.get(j)] == false)
								break;
								
						if(j == nfl.size())
						{
							for(j = 0; j < nfl.size(); j++)
							{
								if(distance[i] < distance[nfl.get(j)] + weight[nfl.get(j)][i])
								{
									distance[i] = distance[nfl.get(j)] + weight[nfl.get(j)][i];
									predecessor[i] = nfl.get(j);
								}
							}
							
							if(distance[i] == -1)
							{
								retValue = false;
								break;
							}
							permanent[i] = true;
							animationStr.add("NE"+predecessor[i]+","+i);
							animationStr.add("V"+i);
							// show message
							if(showMessages)
								messagePanel.append("\n" + G.getVertex(i).getName() + " is made permanent, with disatnce " + distance[i] + " through vertex " + G.getVertex(predecessor[i]).getName() + ".");
							break;
						}
					}
				}
			}while(!permanent[t]  && retValue);
			
			if(retValue == true)
			{
				// show message
				if(showMessages)
					messagePanel.append("\nBack tracking from " + G.getVertex(t).getName() + " to " + G.getVertex(s).getName() + " for knowing the path.");	
				i = 0;
				revpath[i] = t;
				do
				{
					revpath[i+1] = predecessor[revpath[i]];
					i++;
				}while(revpath[i] != s);
				j = i;
				// show message
				if(showMessages)
					messagePanel.append("\n Path : ");
				for(i = 0; i <= j; i++)
				{
					// show message
					if(showMessages)
						messagePanel.append(G.getVertex(revpath[j-i]).getName() + " ");
					path.add(revpath[j-i]);
				}
				
				animationStr.add("R");
			
				for(i = 0; i <= j-1; i++)
				{
					animationStr.add("V"+path.get(i));
					animationStr.add("NE"+path.get(i)+","+path.get(i+1));
				}
				animationStr.add("V"+path.get(i));
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.LongestPath");
		}
		
		animationStr.add("END");
		
		if(!retValue)
			if(showMessages)
				messagePanel.append("\n" + "Unable to find longest path.");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");
			
		return retValue;	
	}

	/**
	 * Euler Tour Algorithm. Finds an Euler tour in the given graph.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph for which the tour has to be found. G should be an undirected graph.
	 * @param tour Is the Integer Vector reference into which the tour is returned as a sequence of vertices to be visited.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 */
	public static void EulerTour(GraphADT<VertexAttr, EdgeAttr> G, Vector<Integer> tour, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		Vector<Integer> T = new Vector<Integer>();
		Vector<Integer> t = new Vector<Integer>();
		int edges[][] = new int[G.numVertices()][G.numVertices()];
		int i,j;
		int i2,k;
		int v;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/EulerTour.txt");
			messagePanel.setText("Start.");
		}
		
		try
		{
			if(G.isDirected() || !isConnected(G))
				throw new GraphAlgException("EulerTour can work on undirected and connected graphs only");
				
			for(i = 0; i < G.numVertices(); i++)
				if(G.inDegree(i) % 2 == 1)
					throw new GraphAlgException("EulerTour doesnot exist in graph with odd degree vertices");
					
			for(i = 0; i < G.numVertices(); i++)
				for(j = 0; j < G.numVertices(); j++)
					if(G.edgeExists(i,j))
						edges[i][j] = 1;
					else
						edges[i][j] = 0;
						
			i = 0;
			T.add(i);
			while(true)
			{
				for(i2 = 0; i2 < G.numVertices(); i2++)
					if(edges[i][i2]==1)
						break;
						
				if(i2 == G.numVertices())
					break;
				else
				{
					edges[i][i2]=0;
					edges[i2][i]=0;
					T.add(i2);
					i = i2;
				}
			}
			// show message
			if(showMessages)
			{
				String Tstr = new String("");
				int Ti;
				for(Ti = 0; Ti < T.size()-1; Ti++)
					Tstr += G.getVertex(T.get(Ti)).getName() + ",";
				Tstr += G.getVertex(T.get(Ti)).getName();
				messagePanel.append("\nT : " + Tstr);
			}
			
			v = 0;
			while(true)
			{
				v = v + 1;
				if(v > G.numEdges())
					break;
					
				i = T.get(v);
				for(i2 = 0; i2 < G.numVertices(); i2++)
					if(edges[i][i2]==1)
						break;
				if(i2 == G.numVertices())
				{
					continue;
				}
				else
				{
					t.clear();
					while(true)
					{
						for(i2 = 0; i2 < G.numVertices(); i2++)
							if(edges[i][i2]==1)
								break;
								
						if(i2 == G.numVertices())
							break;
						else
						{
							edges[i][i2]=0;
							edges[i2][i]=0;
							t.add(i2);
							i = i2;
						}
					}
					
					// show message
					if(showMessages)
					{
						String tstr = new String("");
						int ti;
						for(ti = 0; ti < t.size()-1; ti++)
							tstr += G.getVertex(t.get(ti)).getName() + ",";
						tstr += G.getVertex(t.get(ti)).getName();
						messagePanel.append("\nnew sub-tour t found : " + tstr);
					}
					
					for(k = 0; k < t.size(); k++)
						T.add(v+k+1, t.get(k));
						
					// show message
					if(showMessages)
					{
						String Tstr = new String("");
						int Ti;
						for(Ti = 0; Ti < T.size()-1; Ti++)
							Tstr += G.getVertex(T.get(Ti)).getName() + ",";
						Tstr += G.getVertex(T.get(Ti)).getName();
						messagePanel.append("\nT after splicing: " + Tstr);
					}
				}
				
			}
			
			for(i = 0; i < T.size(); i++)
				tour.add(T.get(i));
				
			for(i = 0; i < T.size()-1; i++)
				animationStr.add("E"+T.get(i)+","+T.get(i+1));
				
			// show message
			if(showMessages)
			{
				String Tstr = new String("");
				int Ti;
				for(Ti = 0; Ti < T.size()-1; Ti++)
					Tstr += G.getVertex(T.get(Ti)).getName() + ",";
				Tstr += G.getVertex(T.get(Ti)).getName();
				messagePanel.append("\nEuler Tour: " + Tstr);
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.EulerTour");
		}

		animationStr.add("END");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");		
	}

	/**
	 * Topological Sort Algorithm.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph on which algorithm is run. G should be directed and acyclic.
	 * @param sortList Is the Integer Vector reference into which the function returns the vertices in topological order.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 */
	public static void TopologicalSort(GraphADT<VertexAttr, EdgeAttr> G, Vector<Integer> sortList, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		int inDegree[] = new int[G.numVertices()];
		boolean progress = true;
		Vector<Integer> nl;
		int i,i2;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/TopologicalSort.txt");
			messagePanel.setText("Start.");
		}
				
		if(!G.isDirected() || !isAcyclic(G))
			throw new GraphAlgException("Topological sort works on directed acyclic graphs only");
		try
		{
			for(i = 0; i < G.numVertices(); i++)
				inDegree[i] = G.inDegree(i);
				
			while(progress)
			{
				progress = false;
				
				for(i = 0; i < G.numVertices(); i++)
				{
					if(inDegree[i] == 0)
					{
						sortList.add(i);
						animationStr.add("V"+i);
						// show message
						if(showMessages)
							messagePanel.append("\n" + G.getVertex(i).getName() + " is selected.");
						progress = true;
						inDegree[i] = -1;
						
						nl = G.getNeighbours(i);
						
						for(i2 = 0; i2 < nl.size(); i2++)
						{
							animationStr.add("Ne"+i+","+nl.get(i2));
							inDegree[nl.get(i2)]--;
						}
					}
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.TopologicalSort");
		}
		
		animationStr.add("R");
		animationStr.add("END");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");
	}
	
	/**
	 * Prim's Minimal Spanning Tree Algorithm.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph on which algorithm is run. G should be undirected.
	 * @param s Is the vetex from which tree construction should start.
	 * @param treeEdges Is the Edge Vector reference into which the function returns the edges of the tree found.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 */
	public static void PrimMST(GraphADT<VertexAttr, EdgeAttr> G, int s, Vector<Edge> treeEdges, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		int edgelist[][] = new int[G.numEdges()][5];
		int eli = 0;
		int min;
		int mini;
		int nv;
		int i,j;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/PrimMST.txt");
			messagePanel.setText("Start.");
		}
				
		if(G.isDirected())
			throw new GraphAlgException("PrimMST works on undirected graphs only");
			
		try
		{
			for(i = 0; i < G.numVertices(); i++)
				for(j = i; j < G.numVertices(); j++)
					if(G.edgeExists(i,j))
					{
						edgelist[eli][0] = i;
						edgelist[eli][1] = j;
						edgelist[eli][2] = G.getEdge(i,j).getWeight();
						edgelist[eli][3] = 1;
						edgelist[eli][4] = 1;
						eli++;
					}
					
			for(i = 0; i < G.numEdges(); i++)
			{
				if(edgelist[i][0] == s)
					edgelist[i][3] = 0;
					
				if(edgelist[i][1] == s)
					edgelist[i][4] = 0;
			}
			
			for(i = 0; i < G.numVertices()-1; i++)
			{
				min = 10000;
				mini = 0;
				for(j = 0; j < eli; j++)
				{
					if((edgelist[j][3] == 0 && edgelist[j][4] == 1) || (edgelist[j][3] == 1 && edgelist[j][4] == 0))
					{
						if(edgelist[j][2] < min)
						{
							min = edgelist[j][2];
							mini = j;
						}
					}
				}
				
				treeEdges.add(new Edge(edgelist[mini][0], edgelist[mini][1]));
				animationStr.add("NV"+edgelist[mini][0]);
				animationStr.add("NV"+edgelist[mini][1]);
				animationStr.add("E"+edgelist[mini][0]+","+edgelist[mini][1]);
				// show message
				if(showMessages)
					messagePanel.append("\nEdge " + "(" + G.getVertex(edgelist[mini][0]).getName() + "," + G.getVertex(edgelist[mini][1]).getName() + ")" + " is selected.");
				
				if(edgelist[mini][3] == 1)
					nv = edgelist[mini][0];
				else
					nv = edgelist[mini][1];
					
				for(j = 0; j < eli; j++)
				{
					if(edgelist[j][0] == nv)
						edgelist[j][3] = 0;
						
					if(edgelist[j][1] == nv)
						edgelist[j][4] = 0;
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.PrimMST");
		}
		
		animationStr.add("END");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");		
	}
	
	/**
	 * Kruskal's Minimal Spanning Tree Algorithm.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph on which algorithm is run. G should be undirected.
	 * @param treeEdges Is the Edge Vector reference into which the function returns the edges of the tree found.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 */
	public static void KruskalMST(GraphADT<VertexAttr, EdgeAttr> G, Vector<Edge> treeEdges, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		int set[] = new int[G.numVertices()];
		int edgelist[][] = new int[G.numEdges()][3];
		int eli = 0;
		int i,j;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/KruskalMST.txt");
			messagePanel.setText("Start.");
		}
		
		if(G.isDirected())
			throw new GraphAlgException("KruskalMST works on undirected graphs only");
			
		for(i = 0; i < G.numVertices(); i++)
			set[i] = i;
			
		try
		{
			for(i = 0; i < G.numVertices(); i++)
				for(j = i; j < G.numVertices(); j++)
					if(G.edgeExists(i,j))
					{
						edgelist[eli][0] = i;
						edgelist[eli][1] = j;
						edgelist[eli][2] = G.getEdge(i,j).getWeight();
						eli++;
					}
				
			// show message
			if(showMessages)
				messagePanel.append("\nSorting edges on edge weights.");
			for(i = 0 ; i < eli ; i++)
				for(j = 0; j < eli-1 ; j++)
					if(edgelist[j][2] > edgelist[j+1][2])
					{
						int t;
						
						t = edgelist[j][0];
						edgelist[j][0] = edgelist[j+1][0];
						edgelist[j+1][0] = t;
						
						t = edgelist[j][1];
						edgelist[j][1] = edgelist[j+1][1];
						edgelist[j+1][1] = t;
						
						t = edgelist[j][2];
						edgelist[j][2] = edgelist[j+1][2];
						edgelist[j+1][2] = t;
					}
					
			for(i = 0; i < eli; i++)
			{
				if(set[edgelist[i][0]] != set[edgelist[i][1]])
				{
					treeEdges.add(new Edge(edgelist[i][0], edgelist[i][1]));
					animationStr.add("NV"+edgelist[i][0]);
					animationStr.add("NV"+edgelist[i][1]);
					animationStr.add("E"+edgelist[i][0]+","+edgelist[i][1]);
					// show message
					if(showMessages)
						messagePanel.append("\nEdge " + "(" + G.getVertex(edgelist[i][0]).getName() + "," + G.getVertex(edgelist[i][1]).getName() + ")" + " is selected.");
					
					int os = set[edgelist[i][1]];
					int ns = set[edgelist[i][0]];
					for(j=0;j<G.numVertices();j++)
						if(set[j] == os)
							set[j] = ns;
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.KruskalMST");
		}
		
		animationStr.add("END");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");		
	}
	
	/**
	 * Dijkstra Shortest Path Algorithm.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph on which algorithm is run. G can be either directed or undirected. The weights should not be negative.
	 * @param s Is the source vertex.
	 * @param t Is the destination vertex.
	 * @param path Is the Integer Vector reference into which the function returns the vertices on the path found.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 * @return True if it is able to find shortest path.
	 */
	public static boolean DijkstraShortestPath(GraphADT<VertexAttr, EdgeAttr> G, int s, int t, Vector<Integer> path, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		boolean permanent[] = new boolean[G.numVertices()];
		int predecessor[] = new int[G.numVertices()];
		int distance[] = new int[G.numVertices()];
		int weight[][] = new int[G.numVertices()][G.numVertices()];
		int revpath[] = new int[G.numVertices()];
		
		int k;
		int i,j;
		int min;

		boolean retValue = true;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/DijkstraShortestPath.txt");
			messagePanel.setText("Start.");
		}
		
		try
		{
			for(i = 0; i < G.numVertices(); i++)
				for(j = 0;j < G.numVertices(); j++)
					if(G.edgeExists(i,j))
						weight[i][j] = G.getEdge(i,j).getWeight();
					else
						weight[i][j] = Integer.MAX_VALUE;
						
			for(i = 0; i < G.numVertices(); i++)
			{
				permanent[i] = false;
				distance[i] = Integer.MAX_VALUE;
			}
			
			k = s;
			permanent[k] = true;
			animationStr.add("V"+k);
			predecessor[k] = -1;
			distance[k] = 0;
			// show message
			if(showMessages)
				messagePanel.append("\n" + G.getVertex(k).getName() + " is made permanent, with disatnce " + distance[k] + ".");
			
			do
			{
				for(i = 0; i < G.numVertices(); i++)
				{
					if(permanent[i] == false && weight[k][i] < Integer.MAX_VALUE && distance[k] + weight[k][i] < distance[i])
					{
						distance[i] = distance[k] + weight[k][i];
						predecessor[i] = k;
						// show message
						if(showMessages)
							messagePanel.append("\n" + G.getVertex(k).getName() + " has got a shorter path, with disatnce " + distance[k] + " through vertex " + G.getVertex(predecessor[i]).getName() + ".");
					}
				}
				
				k = 0;
				min = Integer.MAX_VALUE;
				for(i = 0; i < G.numVertices(); i++)
				{
					if(permanent[i] == false && distance[i] < min  )
					{
						min = distance[i];
						k = i;
					}
				}
				if(min == Integer.MAX_VALUE)
				{
					retValue = false;
					break;
				}
				permanent[k] = true;
				animationStr.add("NE"+predecessor[k]+","+k);
				animationStr.add("V"+k);
				// show message
				if(showMessages)
					messagePanel.append("\n" + G.getVertex(k).getName() + " is made permanent, with disatnce " + distance[k] + " through vertex " + G.getVertex(predecessor[k]).getName() + ".");
				
			} while( k != t);

			
			if(retValue == true)
			{
				// show message
				if(showMessages)
					messagePanel.append("\nBack tracking from " + G.getVertex(t).getName() + " to " + G.getVertex(s).getName() + " for knowing the path.");			
				i = 0;
				revpath[i] = t;
				do
				{
					revpath[i+1] = predecessor[revpath[i]];
					i++;
				}while(revpath[i] != s);
				j = i;
				// show message
				if(showMessages)
					messagePanel.append("\n Path : ");
				for(i = 0;i <= j; i++)
				{
					// show message
					if(showMessages)
						messagePanel.append(G.getVertex(revpath[j-i]).getName() + " ");
					path.add(revpath[j-i]);
				}
				
				animationStr.add("R");
			
				for(i = 0; i < path.size()-1; i++)
				{
					animationStr.add("V"+path.get(i).intValue());
					animationStr.add("NE"+path.get(i).intValue()+","+path.get(i+1).intValue());
				}
				animationStr.add("V"+path.get(i).intValue());
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.DijkstraShortestPath");
			retValue = false;
		}
		
		animationStr.add("END");

		if(!retValue)
			if(showMessages)
				messagePanel.append("\n" + "Unable to find shortest path.");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");

		return retValue;		
	}
	
	/**
	 * Depth First Search. All the vertices reachable from "v" will only be considered.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph on which algorithm is run. G can be either directed or undirected.
	 * @param v Is the vertex from which DFS should start.
	 * @param preOrder Is the Integer Vector reference into which the function returns vertices in the preorder visited.
	 * @param postOrder Is the Integer Vector reference into which the function returns vertices in the postorder visited.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 */
	public static void DFS(GraphADT<VertexAttr, EdgeAttr> G, int v, Vector<Integer> preOrder, Vector<Integer> postOrder, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		Stack<Integer> s = new Stack<Integer>();
		boolean visited[] = new boolean[G.numVertices()];
		Vector<Integer> nl = new Vector<Integer>(10,10);
		int currv;
		int i,i2;
		int oldv;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/DFS.txt");
			messagePanel.setText("Start.");
		}
		
		for(i = 0; i < G.numVertices(); i++)
			visited[i] = false;
			
		try
		{
			while(true)
			{
				s.push(v);
				// show message
				if(showMessages)
					messagePanel.append("\nStarting DFS from " + G.getVertex(v).getName() + ".\n" + G.getVertex(v).getName() + " pushed into S.");
				visited[v] = true;
				// show message
				if(showMessages)
					messagePanel.append("\n" + "visited " + G.getVertex(v).getName() + ".");
				animationStr.add("V"+v);
				preOrder.add(v);
				
				nl = G.getNeighbours(v);
				
				for(i=0;i<nl.size();i++)
					if(visited[nl.get(i)] == false)
						break;
				if(i!=nl.size())
				{
					oldv = v;
					v = nl.get(i);
					animationStr.add("NE"+oldv+","+v);
				}
				else
					break;
			}
			
			while(true)
			{
				if(s.empty() == true)
					break;
				else
					v = s.peek();
					
				nl = G.getNeighbours(v);
				
				for(i=0;i<nl.size();i++)
					if(visited[nl.get(i)] == false)
						break;
				if(i!=nl.size())
				{
					oldv = v;
					v = nl.get(i);
					animationStr.add("NE"+oldv+","+v);
					
					while(true)
					{
						s.push(v);
						// show message
						if(showMessages)
							messagePanel.append("\nStarting DFS from " + G.getVertex(v).getName() + ".\n" + G.getVertex(v).getName() + " pushed into S.");
						visited[v] = true;
						// show message
						if(showMessages)
							messagePanel.append("\n" + "visited " + G.getVertex(v).getName() + ".");						
						animationStr.add("V"+v);
						preOrder.add(v);
						
						nl = G.getNeighbours(v);
						
						for(i2=0;i2<nl.size();i2++)
							if(visited[nl.get(i2)] == false)
								break;
						if(i2!=nl.size())
						{
							oldv = v;
							v = nl.get(i2);
							animationStr.add("NE"+oldv+","+v);
						}
						else
							break;
					}
				}
				else
				{
					// show message
					if(showMessages)
						messagePanel.append("\n" + G.getVertex(s.peek()).getName() + " popped from S.\nCompleted DFS from " + G.getVertex(s.peek()).getName() + ".");
					postOrder.add(s.pop());
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.DFS");
		}
		
		animationStr.add("END");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");		
	}
	
	/**
	 * Breadth First Search. All the vertices reachable from "v" will only be considered.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph on which algorithm is run. G can be either directed or undirected.
	 * @param v Is the vertex from which BFS should start.
	 * @param levelOrder Is the Integer Vector reference into which the function returns vertices in the order visited.
	 * @param animationStr Is the String Vector reference into which the function returns the animation string for the current execution of the algorithm.
	 * @param showMessages If this is true, the algorithm displays its help and messages 
	 */
	public static void BFS(GraphADT<VertexAttr, EdgeAttr> G, int v, Vector<Integer> levelOrder, Vector<String> animationStr, boolean showMessages) throws GraphAlgException
	{
		Queue<Integer> q = new Queue<Integer>();
		boolean visited[] = new boolean[G.numVertices()];
		Vector<Integer> nl;
		int currv;
		int i;
		
		// show help and clear message
		if(showMessages)
		{
			showHelp("help/BFS.txt");
			messagePanel.setText("Start.");
		}
		
		for(i = 0; i < G.numVertices(); i++)
			visited[i] = false;
			
		try
		{
			q.insert(v);
			// show message
			if(showMessages)
				messagePanel.append("\n" + G.getVertex(v).getName() + " inserted into Q.");
			visited[v] = true;
			// show message
			if(showMessages)
				messagePanel.append("\n" + "visited " + G.getVertex(v).getName() + ".");
			animationStr.add("V"+v);
		
			while(q.isEmpty() == false)
			{
				currv = q.delete();
				// show message
				if(showMessages)
					messagePanel.append("\n" + G.getVertex(currv).getName() + " deleted from Q.");
				levelOrder.add(currv);
				
				nl = G.getNeighbours(currv);

				// show message
				if(showMessages)
					messagePanel.append("\n" + "visiting unvisited neighbours of " + G.getVertex(currv).getName() + ".");
				for(i = 0; i < nl.size(); i++)
				{
					if(visited[nl.get(i)] == false)
					{
						q.insert(nl.get(i));
						// show message
						if(showMessages)
							messagePanel.append("\n" + G.getVertex(nl.get(i)).getName() + " inserted into Q.");
						visited[nl.get(i)] = true;
						// show message
						if(showMessages)
							messagePanel.append("\n" + "visited " + G.getVertex(nl.get(i)).getName() + ".");
						
						animationStr.add("NE"+currv+","+nl.get(i));
						animationStr.add("V"+nl.get(i));
					}
				}
			}
		}
		catch(IllegalVertexException e)
		{
			System.out.println("Check error in GraphAlg.BFS");
		}
		
		animationStr.add("END");
		// show message
		if(showMessages)
			messagePanel.append("\n" + "End.");
	}
	
	/**
	 * Returns true if the graph doesnot contain any cycle.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph on which test for cycle is to be done. G can be directed or undirected.
	 */
	public static boolean isAcyclic(GraphADT<VertexAttr, EdgeAttr> G) throws GraphAlgException
	{
		if(G.isDirected())
		{
			Vector<Integer> preOrder = new Vector<Integer>();
			Vector<Integer> postOrder = new Vector<Integer>();
			int preOrderNum[] = new int[G.numVertices()];
			int postOrderNum[] = new int[G.numVertices()];
			boolean span[] = new boolean[G.numVertices()];
			Vector<Integer> nl;
			int cnt;
			int i, j, k, u;
			Vector<String> as = new Vector<String>();
			
			try
			{
				for (i = 0; i < G.numVertices(); i++)
				{
					if(span[i])
						continue;
					
					preOrder.clear();
					postOrder.clear();
					DFS(G, i, preOrder, postOrder, as, false);
					
					cnt = preOrder.size();
						
					for(j = 0; j < preOrder.size(); j++)
						preOrderNum[preOrder.get(j)] = j;
						
					for(j = 0; j < postOrder.size(); j++)
						postOrderNum[postOrder.get(j)] = j;
						
					for(j = 0; j < G.numVertices(); j++)
					{
						if(preOrderNum[j] > 0)
							span[j] = true;
							
						nl = G.getNeighbours(j);
						
						for(k = 0; k < nl.size(); k++)
						{
							u = nl.get(k);
							
							if(preOrderNum[u] < preOrderNum[j] && postOrderNum[u] > postOrderNum[j])
								return false;
						}
					}
					
					if(cnt == G.numVertices())
						break;
				}
				return true;
			}
			catch(IllegalVertexException e)
			{
				System.out.println("Check error in GraphAlg.isAcyclic");
			}
		}
		else
		{
			int n = G.numVertices();
			int m = G.numEdges();
			
			if(m >= n)
				return false;
				
			Vector<Integer> preOrder = new Vector<Integer>();
			Vector<Integer> postOrder = new Vector<Integer>();
			Vector<String> as = new Vector<String>();
			boolean visited[] = new boolean[n];
			
			int components = 0;
			
			for (int i = 0; i < n; i++)    
			{
				if(visited[i])
					continue;
					
				preOrder.clear();
				postOrder.clear();
				DFS(G, i, preOrder, postOrder, as, false); 
				
				for(int j = 0; j < preOrder.size(); j++)
					visited[preOrder.get(j)] = true;
					
				components++;
			}
			
			if(n == m + components)
				return true;
			else
				return false;
		}
		return false;
	}
	
	/**
	 * Returns true for connected undirected graphs and weakly connected directed graphs.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph whose connectivity should be tested. G can be directed or undirected.
	 */
	public static boolean isConnected(GraphADT<VertexAttr, EdgeAttr> G) throws GraphAlgException
	{
		if(G.isDirected())
		{
			try
			{
				Graph uG = new Graph(Graph.UNDIRECTED);
				Vector<Integer> preOrder = new Vector<Integer>();
				Vector<Integer> postOrder = new Vector<Integer>();
				Vector<String> as = new Vector<String>();
				int count;
				int i,j;
				
				for(i = 0; i < G.numVertices(); i++)
					uG.addVertex(new VertexAttr(G.getVertex(i)));
					
				for(i = 0; i < G.numVertices(); i++)
					for(j = 0; j < G.numVertices(); j++)
						if(G.edgeExists(i,j))
							uG.addEdge(i,j,new EdgeAttr(G.getEdge(i,j)));
							
				GraphAlg.DFS(uG, 0, preOrder, postOrder, as, false);
				
				count = preOrder.size();
				if(count == uG.numVertices())
					return true;
				else
					return false;
			}
			catch(IllegalVertexException e)
			{
				System.out.println("Check error in GraphAlg.isStronglyConnected");
			}
			return false;
		}
		else
		{
			Vector<Integer> preOrder = new Vector<Integer>();
			Vector<Integer> postOrder = new Vector<Integer>();
			Vector<String> as = new Vector<String>();
			int count;
			
			GraphAlg.DFS(G, 0, preOrder, postOrder, as, false);
			
			count = preOrder.size();
			if(count == G.numVertices())
				return true;
			else
				return false;
		}
	}
	
	/**
	 * Returns true for connected undirected graphs and strongly connected directed graphs.
	 * @throws GraphAlgException When it is unable to execute algorithm for some reason, with a brief description in case of error.
	 * @param G Is the graph whose connectivity should be tested. G can be directed or undirected.
	 */
	public static boolean isStronglyConnected(GraphADT<VertexAttr, EdgeAttr> G) throws GraphAlgException
	{
		if(G.isDirected())
		{
			try
			{
				Graph R = new Graph(Graph.DIRECTED);
				Vector<Integer> preOrder = new Vector<Integer>();
				Vector<Integer> postOrder = new Vector<Integer>();
				Vector<String> as = new Vector<String>();
				int count;
				int i,j;
				
				GraphAlg.DFS(G, 0, preOrder, postOrder, as, false);
				
				count = preOrder.size();
				if(count < G.numVertices())
					return false;
					
				// create G with reversed arcs
				for(i = 0; i < G.numVertices(); i++)
					R.addVertex(new VertexAttr(G.getVertex(i)));
					
				for(i = 0; i < G.numVertices(); i++)
					for(j = 0; j < G.numVertices(); j++)
						if(G.edgeExists(i,j))
							R.addEdge(j,i,new EdgeAttr(G.getEdge(i,j)));
							
				GraphAlg.DFS(R, 0, preOrder, postOrder, as, false);
				
				count = preOrder.size();
				if(count == G.numVertices())
					return true;
				else
					return false;
			}
			catch(IllegalVertexException e)
			{
				System.out.println("Check error in GraphAlg.isStronglyConnected");
			}
			return false;
		}
		else
		{
			Vector<Integer> preOrder = new Vector<Integer>();
			Vector<Integer> postOrder = new Vector<Integer>();
			Vector<String> as = new Vector<String>();
			int count;
			
			GraphAlg.DFS(G, 0, preOrder, postOrder, as, false);
			
			count = preOrder.size();
			if(count == G.numVertices())
				return true;
			else
				return false;
		}
	}
}